{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Expressive Words"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #array #two-pointers #string"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #数组 #双指针 #字符串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: expressiveWords"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #情感丰富的文字"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>有时候人们会用重复写一些字母来表示额外的感受，比如 <code>\"hello\" -&gt; \"heeellooo\"</code>, <code>\"hi\" -&gt; \"hiii\"</code>。我们将相邻字母都相同的一串字符定义为相同字母组，例如：\"h\", \"eee\", \"ll\", \"ooo\"。</p>\n",
    "\n",
    "<p>对于一个给定的字符串 S ，如果另一个单词能够通过将一些字母组扩张从而使其和 S 相同，我们将这个单词定义为可扩张的（stretchy）。扩张操作定义如下：选择一个字母组（包含字母&nbsp;<code>c</code>&nbsp;），然后往其中添加相同的字母&nbsp;<code>c</code>&nbsp;使其长度达到 3 或以上。</p>\n",
    "\n",
    "<p>例如，以&nbsp;\"hello\" 为例，我们可以对字母组&nbsp;\"o\" 扩张得到 \"hellooo\"，但是无法以同样的方法得到 \"helloo\" 因为字母组 \"oo\" 长度小于&nbsp;3。此外，我们可以进行另一种扩张 \"ll\" -&gt; \"lllll\" 以获得&nbsp;\"helllllooo\"。如果&nbsp;<code>s = \"helllllooo\"</code>，那么查询词&nbsp;\"hello\" 是可扩张的，因为可以对它执行这两种扩张操作使得&nbsp;<code>query = \"hello\" -&gt; \"hellooo\" -&gt;&nbsp;\"helllllooo\" = s</code>。</p>\n",
    "\n",
    "<p>输入一组查询单词，输出其中可扩张的单词数量。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> \n",
    "s = \"heeellooo\"\n",
    "words = [\"hello\", \"hi\", \"helo\"]\n",
    "<strong>输出：</strong>1\n",
    "<strong>解释</strong>：\n",
    "我们能通过扩张 \"hello\" 的 \"e\" 和 \"o\" 来得到 \"heeellooo\"。\n",
    "我们不能通过扩张 \"helo\" 来得到 \"heeellooo\" 因为 \"ll\" 的长度小于 3 。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length, words.length &lt;= 100</code></li>\n",
    "\t<li><code>1 &lt;= words[i].length &lt;= 100</code></li>\n",
    "\t<li><font color=\"#c7254e\" face=\"Menlo, Monaco, Consolas, Courier New, monospace\"><span style=\"font-size: 12.6px; background-color: rgb(249, 242, 244);\">s</span></font> 和所有在&nbsp;<code>words</code>&nbsp;中的单词都只由小写字母组成。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [expressive-words](https://leetcode.cn/problems/expressive-words/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [expressive-words](https://leetcode.cn/problems/expressive-words/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"heeellooo\"\\n[\"hello\", \"hi\", \"helo\"]', '\"zzzzzyyyyy\"\\n[\"zzyy\",\"zy\",\"zyy\"]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        charlist = []\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            j = i\n",
    "            temp = 1\n",
    "            while  j+1 < len(s) and s[j] == s[j+1]:\n",
    "                j += 1\n",
    "                temp += 1\n",
    "            charlist.append([s[i],temp])\n",
    "            i = j+1\n",
    "        target = 0\n",
    "        for x in words :\n",
    "            i = 0\n",
    "            j = 0 \n",
    "            k = 0\n",
    "            while i < len(x):\n",
    "                ans = 1\n",
    "                if j < len(charlist) and x[i] == charlist[j][0] :\n",
    "                    k = i\n",
    "                    while k+1 < len(x) and x[k] == x[k+1] : \n",
    "                        k += 1\n",
    "                        ans += 1\n",
    "                    if ans == charlist[j][1] or (charlist[j][1] >= 3 and charlist[j][1] > ans) :\n",
    "                        i = k+1\n",
    "                        j += 1\n",
    "                    else :\n",
    "                        break\n",
    "                else :\n",
    "                    break\n",
    "            else:\n",
    "                if j == len(charlist):\n",
    "                    target += 1\n",
    "        return target\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        count = 0\n",
    "        for word in words:\n",
    "            i, j = 0, 0\n",
    "            flag = 1\n",
    "            while j < len(s) and i < len(word) and flag == 1:\n",
    "                if word[i] != s[j]:\n",
    "                    flag = 0\n",
    "                a, b = i, j\n",
    "                while a < len(word) and word[a] == word[i]:\n",
    "                    a += 1\n",
    "                while b < len(s) and s[b] == s[j]:\n",
    "                    b += 1\n",
    "                a, b = a - i, b - j\n",
    "                if a != b and (a > b or b < 3):\n",
    "                    flag = 0\n",
    "                i, j = i + a, j + b\n",
    "            if flag == 1 and i == len(word) and j == len(s):\n",
    "                count += 1\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def check(s, t):\n",
    "            m, n = len(s), len(t)\n",
    "            if n > m:\n",
    "                return False\n",
    "            i = j = 0\n",
    "            while i < m and j < n:\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                k = i\n",
    "                while k < m and s[k] == s[i]:\n",
    "                    k += 1\n",
    "                c1 = k - i\n",
    "                i, k = k, j\n",
    "                while k < n and t[k] == t[j]:\n",
    "                    k += 1\n",
    "                c2 = k - j\n",
    "                j = k\n",
    "                if c1 < c2 or (c1 < 3 and c1 != c2):\n",
    "                    return False\n",
    "            return i == m and j == n\n",
    "\n",
    "        return sum(check(s, t) for t in words)\n",
    "\n",
    "                \n",
    "            \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        ans = 0\n",
    "        for w in words:\n",
    "            i, j = 0, 0\n",
    "            flag = True\n",
    "            while i < len(s) and j < len(w):\n",
    "                if s[i] != w[j]:\n",
    "                    flag = False\n",
    "                \n",
    "                ch = s[i]\n",
    "                cnti = 0\n",
    "                while i < len(s) and s[i] == ch:\n",
    "                    cnti += 1\n",
    "                    i += 1\n",
    "                cntj = 0\n",
    "                while j < len(w) and w[j] == ch:\n",
    "                    cntj += 1\n",
    "                    j += 1\n",
    "\n",
    "\n",
    "                if cnti < cntj:\n",
    "                    flag = False\n",
    "\n",
    "                if cnti != cntj and cnti < 3:\n",
    "                    flag = False\n",
    "\n",
    "            if flag and i == len(s) and j == len(w):\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        #copy\n",
    "        def check(s,t):\n",
    "            m,n = len(s),len(t)\n",
    "            if n >m:\n",
    "                return False\n",
    "            i=j=0\n",
    "            while i <m and j <n:\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                k = i\n",
    "                while k <m and s[k] == s[i]:\n",
    "                    k +=1\n",
    "                c1= k-i\n",
    "                i,k = k,j\n",
    "                while k <n and t[k]== t[j]:\n",
    "                    k +=1\n",
    "                c2 = k-j\n",
    "                j = k\n",
    "                if c1 < c2 or(c1<3 and c1!= c2):\n",
    "                    return False\n",
    "\n",
    "            return i==m and j==n\n",
    "        return sum(check(s,t) for t in words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        res = 0\n",
    "        for word in words:\n",
    "            if len(word) > len(s):\n",
    "                continue\n",
    "\n",
    "            i = j = 0\n",
    "            is_match = True\n",
    "            while i < len(word) and j < len(s):\n",
    "                if word[i] != s[j]:\n",
    "                    is_match = False\n",
    "                    break\n",
    "\n",
    "                m = i\n",
    "                while m < len(word) and word[i] == word[m]:\n",
    "                    m += 1\n",
    "                \n",
    "                cnt1 = m - i \n",
    "\n",
    "                n = j\n",
    "                while n < len(s) and  s[j] == s[n]:\n",
    "                    n += 1\n",
    "\n",
    "                cnt2 = n - j \n",
    "                if  cnt1 > cnt2 or (cnt1 < cnt2 and cnt2 <=2):\n",
    "                    is_match = False\n",
    "                    break\n",
    "                i = m\n",
    "                j = n\n",
    "\n",
    "            if is_match and i == len(word) and j == len(s):\n",
    "                res += 1\n",
    "                \n",
    "        return res\n",
    "\n",
    "                    \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        ret = 0\n",
    "        def check(s):\n",
    "            cnt = []\n",
    "            left, right = 0, 1\n",
    "            while right < len(s):\n",
    "                if s[right-1] != s[right]:\n",
    "                    cnt.append(s[left: right])\n",
    "                    left = right\n",
    "                right += 1\n",
    "            cnt.append(s[left:])\n",
    "            return cnt\n",
    "        cnt_s = check(s)\n",
    "        for word in words:\n",
    "            cnt_w = check(word)\n",
    "            i = j = 0\n",
    "            while i < len(cnt_w) and j < len(cnt_s):\n",
    "                m, n = len(cnt_w[i]), len(cnt_s[j])\n",
    "                if cnt_w[i][0] != cnt_s[j][0]:\n",
    "                    break\n",
    "                if (n < 3 and m == n) or (n >= 3 and 0 < m <= n):\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(cnt_w) and j == len(cnt_s):\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "\n",
    "        def treat(s):\n",
    "            n = len(s)\n",
    "            s += ' '\n",
    "            f = {}\n",
    "            idx, i, j = 0, 0, 0\n",
    "            while i < n:\n",
    "                for j in range(i, n+1):\n",
    "                    if s[i] != s[j]:\n",
    "                        f[idx] = [s[i], j-i] # [0] = char, [1] = len\n",
    "                        idx += 1\n",
    "                        i = j\n",
    "                        break\n",
    "            # print(f)\n",
    "            return f\n",
    "        \n",
    "        base = treat(s)\n",
    "        n = len(base)\n",
    "        ans = 0\n",
    "        for str0 in words:\n",
    "            tmp = treat(str0)\n",
    "            if n != len(tmp):\n",
    "                continue\n",
    "            needadd = True\n",
    "            for i in range(n):\n",
    "                if base[i][0] != tmp[i][0] or \\\n",
    "                (base[i][1] < 3 and tmp[i][1] != base[i][1]) or \\\n",
    "                base[i][1] < tmp[i][1]:\n",
    "                    needadd = False\n",
    "                    break\n",
    "            \n",
    "            if needadd:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        ret = 0\n",
    "        def check(s):\n",
    "            cnt = []\n",
    "            left, right = 0, 1\n",
    "            while right < len(s):\n",
    "                if s[right-1] != s[right]:\n",
    "                    cnt.append(s[left: right])\n",
    "                    left = right\n",
    "                right += 1\n",
    "            cnt.append(s[left:])\n",
    "            return cnt\n",
    "        cnt_s = check(s)\n",
    "        for word in words:\n",
    "            cnt_w = check(word)\n",
    "            i = j = 0\n",
    "            while i < len(cnt_w) and j < len(cnt_s):\n",
    "                m, n = len(cnt_w[i]), len(cnt_s[j])\n",
    "                if cnt_w[i][0] != cnt_s[j][0]:\n",
    "                    break\n",
    "                if m == n < 3 or 0 < m <= n >= 3:\n",
    "                    i += 1\n",
    "                j += 1\n",
    "            if i == len(cnt_w) and j == len(cnt_s):\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sep_seg(self,s:str)->list:\n",
    "        l = len(s)\n",
    "        if l<=1:\n",
    "            return s\n",
    "        begin = 0\n",
    "        s+=\"/n\"\n",
    "        segments = []\n",
    "        for i in range(1,l+1):\n",
    "            if s[i]!=s[i-1]:\n",
    "                segments.append(s[begin:i])\n",
    "                begin = i\n",
    "        return segments    \n",
    "\n",
    "\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        s_segments = self.sep_seg(s)\n",
    "        print(s_segments)\n",
    "        ans = 0\n",
    "        for word in words:\n",
    "            w_segments = self.sep_seg(word)\n",
    "            print(w_segments)\n",
    "            if len(w_segments) != len(s_segments):\n",
    "                continue\n",
    "            for i in range(len(w_segments)):\n",
    "                if len(s_segments[i]) < len(w_segments[i]):\n",
    "                    break\n",
    "                if s_segments[i][0] != w_segments[i][0]:\n",
    "                    break\n",
    "                if s_segments[i]!=w_segments[i] and len(s_segments[i])<3:\n",
    "                    break\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def check(str1 , str2):\n",
    "            i , j = 0 , 0\n",
    "            while i < len(str1) and j < len(str2):\n",
    "                if str1[i] != str2[j]:\n",
    "                    return False\n",
    "                cnti = 0\n",
    "                ch = str1[i]\n",
    "                while i < len(str1) and str1[i] == ch:\n",
    "                    cnti += 1\n",
    "                    i += 1\n",
    "                cntj = 0\n",
    "                while j < len(str2) and str2[j] == ch:\n",
    "                    cntj += 1\n",
    "                    j += 1\n",
    "                if cnti < cntj:\n",
    "                    return False\n",
    "                if cnti != cntj and cnti < 3:\n",
    "                    return False\n",
    "            return i == len(str1) and j == len(str2)\n",
    "        res = 0\n",
    "        for i in words:\n",
    "            if check(s , i):\n",
    "                res += 1\n",
    "        return res\n",
    "        \n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        n = len(s)\n",
    "        i, x = 0, []\n",
    "        while i < n:\n",
    "            j = i\n",
    "            while j+1 < n and s[j+1] == s[i]:\n",
    "                j += 1\n",
    "            if j-i+1 >= 3:\n",
    "                a, b = 1, j-i+1\n",
    "            else:\n",
    "                a = b = j-i+1\n",
    "            x.append([s[i], a, b])\n",
    "            i = j+1\n",
    "\n",
    "        n = len(x)\n",
    "        ans = 0\n",
    "        for w in words:\n",
    "            m = len(w)\n",
    "            i = k = 0\n",
    "            stretchy = True\n",
    "            while i < m and k < n:\n",
    "                j = i\n",
    "                while j+1 < m and w[j+1] == w[i]:\n",
    "                    j += 1\n",
    "                if w[i] != x[k][0] or j-i+1 < x[k][1] or j-i+1 > x[k][2]:\n",
    "                    stretchy = False\n",
    "                    break\n",
    "                k += 1\n",
    "                i = j+1\n",
    "            ans += (stretchy and i == m and k == n)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def expand(s, t):\n",
    "            i = j = 0\n",
    "            while i < len(s) and j < len(t):\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                ch = s[i]\n",
    "                cnti = 0\n",
    "                while i < len(s) and s[i] == ch:\n",
    "                    cnti += 1\n",
    "                    i += 1\n",
    "                cntj = 0\n",
    "                while j < len(t) and t[j] == ch:\n",
    "                    cntj += 1\n",
    "                    j += 1\n",
    "                if cnti < cntj:\n",
    "                    return False\n",
    "                if cnti != cntj and cnti < 3:\n",
    "                    return False\n",
    "            return i == len(s) and j == len(t)\n",
    "        return sum(int(expand(s, word)) for word in words)\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "\n",
    "        def valid(s: str, word: str):\n",
    "            n = len(s)\n",
    "            m = len(word)\n",
    "            i = j = 0\n",
    "            while i < n and j < m:\n",
    "                if s[i] != word[j]:\n",
    "                    return False\n",
    "                i0 = i\n",
    "                while i0 < n and s[i0] == s[i]:\n",
    "                    i0 += 1\n",
    "                j0 = j\n",
    "                while j0 < m and word[j0] == word[j]:\n",
    "                    j0 += 1\n",
    "                cnt = i0 - i - j0 + j\n",
    "                if cnt < 0 or (cnt != 0 and i0 - i < 3):\n",
    "                    return False\n",
    "                i = i0\n",
    "                j = j0\n",
    "            if i != n or j != m:\n",
    "                return False\n",
    "            return True\n",
    "        ans = 0\n",
    "        for word in words:\n",
    "            ans += valid(s, word)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def expand(s: str, t: str) -> bool:\n",
    "            i = j = 0\n",
    "            while i < len(s) and j < len(t):\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                ch = s[i]\n",
    "                cnti = 0\n",
    "                while i < len(s) and s[i] == ch:\n",
    "                    cnti += 1\n",
    "                    i += 1\n",
    "                cntj = 0\n",
    "                while j < len(t) and t[j] == ch:\n",
    "                    cntj += 1\n",
    "                    j += 1\n",
    "                \n",
    "                if cnti < cntj:\n",
    "                    return False\n",
    "                if cnti != cntj and cnti < 3:\n",
    "                    return False\n",
    "            \n",
    "            return i == len(s) and j == len(t)\n",
    "        \n",
    "        return sum(int(expand(s, word)) for word in words)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        word = []\n",
    "        n = len(s)\n",
    "        c = s[0]\n",
    "        cnt = 0\n",
    "        i = 0\n",
    "        while i < n:\n",
    "            while i < n and c == s[i]:\n",
    "                cnt += 1\n",
    "                i += 1\n",
    "            word.append((c, cnt))\n",
    "\n",
    "            if i < n:\n",
    "                c = s[i]\n",
    "                cnt = 0\n",
    "\n",
    "        # print(word)\n",
    "        res = 0\n",
    "        for i in range(len(words)):\n",
    "            w = words[i]\n",
    "            m = len(w)\n",
    "            c = w[0]\n",
    "            cnt = 0\n",
    "            j = 0\n",
    "            tmp = []\n",
    "            isMatch = True\n",
    "            while j < m:\n",
    "                while j < m and c == w[j]:\n",
    "                    cnt += 1\n",
    "                    j += 1\n",
    "\n",
    "                lentmp = len(tmp)\n",
    "                if lentmp >= len(word):\n",
    "                    isMatch = False\n",
    "                    break\n",
    "                c1, cnt1 = word[len(tmp)]\n",
    "                # print(w, c, cnt, c1, cnt1)\n",
    "                if c1 != c or not (cnt1 == cnt or (cnt1 > cnt and cnt1 >= 3)):\n",
    "                    isMatch = False\n",
    "                    break\n",
    "                if j < m:\n",
    "                    c = w[j]\n",
    "                    cnt = 0\n",
    "                tmp.append((c1, cnt1))\n",
    "\n",
    "            if len(tmp) == len(word) and isMatch:\n",
    "                res += 1\n",
    "\n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        sn = len(set(s))\n",
    "        s_list = [0]\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] != s[i-1]:\n",
    "                s_list.append(i)\n",
    "\n",
    "        count = 0\n",
    "        for item in words:\n",
    "            ni = len(set(item))\n",
    "            if ni != sn:\n",
    "                continue\n",
    "            i_list = [0]\n",
    "            for i in range(1, len(item)):\n",
    "                if item[i] != item[i-1]:\n",
    "                    i_list.append(i)\n",
    "            #print(item)\n",
    "            #print(s_list,i_list)\n",
    "            if len(s_list) != len(i_list):\n",
    "                continue\n",
    "            nc = len(s_list)\n",
    "            flag = False\n",
    "            if nc == 1:\n",
    "                if len(s) == len(item) or (len(s) >= 3 and len(s) > len(item)):\n",
    "                    flag = True\n",
    "                else:\n",
    "                    continue\n",
    "            for i in range(nc):\n",
    "                if s[s_list[i]] != item[i_list[i]]:\n",
    "                    flag = True\n",
    "                    break\n",
    "                if i == nc - 1:\n",
    "                    num_s = len(s) - s_list[i]\n",
    "                    num_i = len(item) - i_list[i]\n",
    "                else:\n",
    "                    num_s = s_list[i+1] - s_list[i]\n",
    "                    num_i = i_list[i+1] - i_list[i]\n",
    "                #print(i,num_s,num_i)\n",
    "                #if num_s != num_i and num_s - num_i < 2:\n",
    "                if num_s != num_i and num_s < 3 or num_s < num_i:\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                count += 1\n",
    "        return count\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sep_seg(self,s:str)->list:\n",
    "        l = len(s)\n",
    "        if l<=1:\n",
    "            return s\n",
    "        begin = 0\n",
    "        s+=\"/n\"\n",
    "        segments = []\n",
    "        for i in range(1,l+1):\n",
    "            if s[i]!=s[i-1]:\n",
    "                segments.append(s[begin:i])\n",
    "                begin = i\n",
    "        return segments    \n",
    "\n",
    "\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        s_segments = self.sep_seg(s)\n",
    "        print(s_segments)\n",
    "        ans = 0\n",
    "        for word in words:\n",
    "            w_segments = self.sep_seg(word)\n",
    "            print(w_segments)\n",
    "            if len(w_segments) != len(s_segments):\n",
    "                continue\n",
    "            for i in range(len(w_segments)):\n",
    "                if len(s_segments[i]) < len(w_segments[i]):\n",
    "                    break\n",
    "                if s_segments[i][0] != w_segments[i][0]:\n",
    "                    break\n",
    "                if s_segments[i]!=w_segments[i] and len(s_segments[i])<3:\n",
    "                    break\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def check(s, t):\n",
    "            m, n = len(s), len(t)\n",
    "            if n > m:\n",
    "                return False\n",
    "            i = j = 0\n",
    "            while i < m and j < n:\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                k = i\n",
    "                while k < m and s[k] == s[i]:\n",
    "                    k += 1\n",
    "                c1 = k - i\n",
    "                i, k = k, j\n",
    "                while k < n and t[k] == t[j]:\n",
    "                    k += 1\n",
    "                c2 = k - j\n",
    "                j = k\n",
    "                if c1 < c2 or (c1 < 3 and c1 != c2):\n",
    "                    return False\n",
    "            return i == m and j == n\n",
    "\n",
    "        return sum(check(s, t) for t in words)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def check_expand(s: str, t: str) -> bool:\n",
    "            i = j = 0\n",
    "            while i < len(s) and j < len(t):\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                ch = s[i]\n",
    "                count = 0\n",
    "                while i < len(s) and s[i] == ch:\n",
    "                    count += 1\n",
    "                    i += 1\n",
    "                countj = 0\n",
    "                while j < len(t) and t[j] == ch:\n",
    "                    countj += 1\n",
    "                    j += 1\n",
    "                if count < countj:\n",
    "                    return False\n",
    "                if count != countj and count < 3:\n",
    "                    return False\n",
    "            return i == len(s) and j == len(t)\n",
    "\n",
    "        return sum(int(check_expand(s, woed)) for woed in words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def check(self, s, w):\r\n",
    "        i , j = 0, 0\r\n",
    "        m, n = len(s), len(w)\r\n",
    "        if m < n:\r\n",
    "            return False\r\n",
    "        while i < m and j < n:\r\n",
    "            # 元素不相等\r\n",
    "            if s[i] != w[j]:\r\n",
    "                return False\r\n",
    "            c1, c2 = 1, 1\r\n",
    "            # 元素相等，计算连续的个数\r\n",
    "            while i + 1 < m and s[i] == s[i + 1]:\r\n",
    "                c1 += 1\r\n",
    "                i += 1\r\n",
    "            while j + 1 < n and w[j] == w[j + 1]:\r\n",
    "                c2 += 1\r\n",
    "                j += 1\r\n",
    "            # 1.w当前连续相同片段长度大于s的，false\r\n",
    "            # 2.如果s的连续个数小于3，那么w的连续个数必须和s的连续个数相等\r\n",
    "            if c2 > c1 or c1 < 3 and c1 != c2:\r\n",
    "                return False\r\n",
    "            i += 1\r\n",
    "            j += 1\r\n",
    "        return i == m and j == n\r\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\r\n",
    "        ans = 0\r\n",
    "        for w in words:\r\n",
    "            if not self.check(s, w):\r\n",
    "                continue\r\n",
    "            ans += 1\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def str2list(st: str):\n",
    "            diversity = []  # 用于存放连续的字母 如better -> [b,e,t,e,r]\n",
    "            number = []  # 用于存放对应字母连续的个数         [1,1,2,1,1]\n",
    "            last = ''\n",
    "            for i in st:\n",
    "                if i == last:\n",
    "                    number[-1] += 1  # 如果与上一个加入的字母相同，表示是连续字母，对应个数加一\n",
    "                else:\n",
    "                    diversity.append(i)  # 如果非连续字母，就添加字母，并添加个数为1\n",
    "                    number.append(1)\n",
    "                    last = i\n",
    "            # print(diversity)\n",
    "            # print(number)\n",
    "            return [diversity, number]\n",
    "\n",
    "        num = 0\n",
    "        lfors = str2list(s)\n",
    "        for i in words:\n",
    "            invalid = 0\n",
    "            lforword = str2list(i)  # 下标0表示diversity，1表示number\n",
    "            if lforword[0] == lfors[0]:\n",
    "                for j in range(len(lforword[0])):\n",
    "                    # print('lforword[1][{}]='.format(j),lforword[1][j],'lfors[1][{}]='.format(j),lfors[1][j])\n",
    "                    if lforword[1][j] == 1 and lfors[1][j] == 2:  # 通过分析如果s中某个字母的个数为2，那么如果word中对应字母为1则表示不能扩展\n",
    "                        invalid = 1\n",
    "                        break\n",
    "                    elif lfors[1][j] < lforword[1][j]:  # 如果word中某个字母的连续长度比s中对应字母还要长，那么相当于‘压缩’了，也不能扩展\n",
    "                        invalid = 1\n",
    "                        break\n",
    "                if invalid == 0:\n",
    "                    # print('{} is valid'.format(lforword))\n",
    "                    num += 1\n",
    "\n",
    "        return num\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def check(s, t):\n",
    "            m, n = len(s), len(t)\n",
    "            if n > m:\n",
    "                return False\n",
    "            i = j = 0\n",
    "            while i < m and j < n:\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                k = i\n",
    "                while k < m and s[k] == s[i]:\n",
    "                    k += 1\n",
    "                c1 = k - i\n",
    "                i, k = k, j\n",
    "                while k < n and t[k] == t[j]:\n",
    "                    k += 1\n",
    "                c2 = k - j\n",
    "                j = k\n",
    "                if c1 < c2 or (c1 < 3 and c1 != c2):\n",
    "                    return False\n",
    "            return i == m and j == n\n",
    "\n",
    "        return sum(check(s, t) for t in words)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def expend(s: str, t:str) -> bool:\n",
    "            i = j = 0\n",
    "            while i < len(s) and j  < len(t):\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                ch = s[i]\n",
    "                cnt_i = 0\n",
    "                while i < len(s) and s[i] == ch:\n",
    "                    cnt_i += 1\n",
    "                    i += 1\n",
    "\n",
    "                cnt_j = 0\n",
    "                while j < len(t) and t[j] == ch:\n",
    "                    cnt_j += 1\n",
    "                    j += 1\n",
    "                if cnt_i < cnt_j:\n",
    "                    return False\n",
    "                if cnt_i != cnt_j and cnt_i < 3:\n",
    "                    return False\n",
    "            return i == len(s) and j == len(t)\n",
    "        return sum(int(expend(s, word)) for word in words)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def check(str1,str2):\n",
    "            i = j = 0\n",
    "            while i < len(str1) and j < len(str2):\n",
    "                if str1[i] != str2[j]:\n",
    "                    return False\n",
    "                ch = str1[i]\n",
    "                cnti = 0\n",
    "                while i < len(str1) and str1[i] == ch:\n",
    "                    cnti += 1\n",
    "                    i += 1\n",
    "                cntj = 0\n",
    "                while j < len(str2) and str2[j] == ch:\n",
    "                    cntj += 1\n",
    "                    j += 1\n",
    "                if cnti < cntj:\n",
    "                    return False\n",
    "                if cnti != cntj and cnti < 3:\n",
    "                    return False\n",
    "            return i == len(str1) and j == len(str2)\n",
    "        res = 0\n",
    "        for i in words:\n",
    "            if check(s,i):\n",
    "                res += 1\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def check(s, t):\n",
    "            m, n = len(s), len(t)\n",
    "            if n > m:\n",
    "                return False\n",
    "            i = j = 0\n",
    "            while i < m and j < n:\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                k = i\n",
    "                while k < m and s[k] == s[i]:\n",
    "                    k += 1\n",
    "                c1 = k - i\n",
    "                i, k = k, j\n",
    "                while k < n and t[k] == t[j]:\n",
    "                    k += 1\n",
    "                c2 = k - j\n",
    "                j = k\n",
    "                if c1 < c2 or (c1 < 3 and c1 != c2):\n",
    "                    return False\n",
    "            return i == m and j == n\n",
    "\n",
    "        return sum(check(s, t) for t in words)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sep_seg(self,s:str)->list:\n",
    "        l = len(s)\n",
    "        if l<=1:\n",
    "            return s\n",
    "        begin = 0\n",
    "        s+=\"/n\"\n",
    "        segments = []\n",
    "        for i in range(1,l+1):\n",
    "            if s[i]!=s[i-1]:\n",
    "                segments.append(s[begin:i])\n",
    "                begin = i\n",
    "        return segments    \n",
    "\n",
    "\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        s_segments = self.sep_seg(s)\n",
    "        print(s_segments)\n",
    "        ans = 0\n",
    "        for word in words:\n",
    "            w_segments = self.sep_seg(word)\n",
    "            print(w_segments)\n",
    "            if len(w_segments) != len(s_segments):\n",
    "                continue\n",
    "            for i in range(len(w_segments)):\n",
    "                if len(s_segments[i]) < len(w_segments[i]):\n",
    "                    break\n",
    "                if s_segments[i][0] != w_segments[i][0]:\n",
    "                    break\n",
    "                if s_segments[i]!=w_segments[i] and len(s_segments[i])<3:\n",
    "                    break\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        sn = len(set(s))\n",
    "        s_list = [0]\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i] != s[i-1]:\n",
    "                s_list.append(i)\n",
    "        count = 0\n",
    "        for item in words:\n",
    "            ni = len(set(item))\n",
    "            if ni != sn:\n",
    "                continue\n",
    "            i_list = [0]\n",
    "            for i in range(1, len(item)):\n",
    "                if item[i] != item[i-1]:\n",
    "                    i_list.append(i)\n",
    "            if len(s_list) != len(i_list):\n",
    "                continue\n",
    "            nc = len(s_list)\n",
    "            flag = False\n",
    "            if nc == 1:\n",
    "                if len(s) == len(item) or (len(s) >= 3 and len(s) > len(item)):\n",
    "                    flag = True\n",
    "                else:\n",
    "                    continue\n",
    "            for i in range(nc):\n",
    "                if s[s_list[i]] != item[i_list[i]]:\n",
    "                    flag = True\n",
    "                    break\n",
    "                if i == nc - 1:\n",
    "                    num_s = len(s) - s_list[i]\n",
    "                    num_i = len(item) - i_list[i]\n",
    "                else:\n",
    "                    num_s = s_list[i+1] - s_list[i]\n",
    "                    num_i = i_list[i+1] - i_list[i]\n",
    "                if num_s != num_i and num_s < 3 or num_s < num_i:\n",
    "                    flag = True\n",
    "                    break\n",
    "            if not flag:\n",
    "                count += 1\n",
    "        return count\n",
    "\n",
    "\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#!/usr/bin/env python\n",
    "# -*- coding:utf-8 -*-\n",
    "# @File    : 情感丰富的文字\n",
    "# @Time    : 2023/10/11 9:08\n",
    "# @Version: 1.0\n",
    "# @License: (C)Copyright 2021-2022, HUAWEI\n",
    "# @Desc:\n",
    "\"\"\"\n",
    "情感丰富的文字.py\n",
    "\"\"\"\n",
    "from typing import List\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def judgeWords(s: str, t: str) -> bool:\n",
    "            i, j = 0, 0\n",
    "            while i < len(s) and j < len(t):\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                ch = s[i]\n",
    "                count_s = 0\n",
    "                while i < len(s) and s[i] == ch:\n",
    "                    count_s += 1\n",
    "                    i += 1\n",
    "                count_t = 0\n",
    "                while j < len(t) and t[j] == ch:\n",
    "                    count_t += 1\n",
    "                    j += 1\n",
    "                if count_t > count_s:\n",
    "                    return False\n",
    "                \n",
    "                if count_t != count_s and count_s < 3:\n",
    "                    return False\n",
    "            return i == len(s) and j == len(t)\n",
    "        return sum(int(judgeWords(s, word)) for word in words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "\n",
    "        def check(s,t ):\n",
    "            i=j=0\n",
    "            while i <len(s) and j < len(t):\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                \n",
    "                ch = s[i]\n",
    "\n",
    "                cnti = 0\n",
    "                while i < len(s) and s[i] == ch:\n",
    "                    cnti += 1\n",
    "                    i += 1\n",
    "                cntj = 0\n",
    "\n",
    "                while j < len(t) and t[j] == ch:\n",
    "                    cntj += 1\n",
    "                    j += 1\n",
    "                if cnti < cntj:\n",
    "                    return False\n",
    "                if cnti != cntj and cnti < 3 :\n",
    "                    return False\n",
    "            \n",
    "            return i == len(s) and j == len(t)\n",
    "        res = 0\n",
    "\n",
    "        for w in words:\n",
    "            if check(s, w):\n",
    "                res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        cnt = Counter(s)\n",
    "        ret = 0\n",
    "        for word in words:\n",
    "            cnt_w = Counter(word)\n",
    "            if cnt_w & cnt == cnt_w:\n",
    "                tmp = 0\n",
    "                for k, v in cnt_w.items():\n",
    "                    if cnt[k] < 3:\n",
    "                        if cnt[k] == v:\n",
    "                            tmp += cnt[k]\n",
    "                    else:\n",
    "                        tmp += cnt[k]\n",
    "                if tmp == len(s):\n",
    "                    ret += 1\n",
    "        return ret\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        ret = 0\n",
    "        \n",
    "        def check(s):\n",
    "            cnt = []\n",
    "            left, right = 0, 1\n",
    "            while right < len(s):\n",
    "                if s[right-1] != s[right]:\n",
    "                    cnt.append(s[left: right])\n",
    "                    left = right\n",
    "                right += 1\n",
    "            cnt.append(s[left:])\n",
    "            return cnt\n",
    "        cnt_s = check(s)\n",
    "        for word in words:\n",
    "            cnt_w = check(word)\n",
    "            i = j = 0\n",
    "            while j < len(cnt_s) and i < len(cnt_w):\n",
    "                m, n = len(cnt_w[i]), len(cnt_s[j])\n",
    "                if cnt_w[i][0] != cnt_s[j][0]:\n",
    "                    break\n",
    "                if n < 3:\n",
    "                    if m == n:\n",
    "                        i += 1\n",
    "                else:\n",
    "                    if 0 < m <= n:\n",
    "                        i += 1\n",
    "                j += 1\n",
    "            if i == len(cnt_w) and j == len(cnt_s):\n",
    "                ret += 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        record = [1] * len(s) \n",
    "        # 记录从后往前连续到此的相同字母个数\n",
    "\n",
    "        for i in range(len(s)-2, -1, -1):\n",
    "            if s[i]==s[i+1]:\n",
    "                record[i] = record[i+1]+1\n",
    "\n",
    "    \n",
    "        res = 0\n",
    "        for word in words:\n",
    "            i,j = 0,0\n",
    "            if len(word)>len(s):\n",
    "                continue\n",
    "            while i<len(s) and j<len(word):\n",
    "                if s[i]==word[j]:\n",
    "                    if record[i]>=3:\n",
    "                        cnt = record[i]-1\n",
    "                        i += record[i]\n",
    "                        j += 1\n",
    "                        while cnt and j<len(word) and word[j]==word[j-1]:\n",
    "                            j += 1\n",
    "                            cnt -= 1\n",
    "\n",
    "                    else:\n",
    "                        i += 1\n",
    "                        j += 1\n",
    "                    \n",
    "                else:\n",
    "                    break\n",
    "\n",
    "            if j==len(word) and i==len(s):\n",
    "                res += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def check(s, t):\n",
    "            m, n = len(s), len(t)\n",
    "            if n > m:\n",
    "                return False\n",
    "            i = j = 0\n",
    "            while i < m and j < n:\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                \n",
    "                k = i\n",
    "                while k < m and s[k] == s[i]:\n",
    "                    k += 1\n",
    "                c1 = k - i\n",
    "                \n",
    "                i, k = k, j\n",
    "                while k < n and t[k] == t[j]:\n",
    "                    k += 1\n",
    "                c2 = k - j\n",
    "                \n",
    "                j = k\n",
    "                if c1 < c2 or (c1 < 3 and c1 != c2):\n",
    "                    return False\n",
    "            return i == m and j == n\n",
    "\n",
    "        return sum(check(s, t) for t in words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def expand(s : str, t: str) -> bool:\n",
    "            i = j = 0\n",
    "            while i < len(s) and j < len(t):\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                ch = s[i]\n",
    "                cnti = 0\n",
    "                while i < len(s) and s[i] == ch:\n",
    "                    cnti += 1\n",
    "                    i += 1\n",
    "                cntj = 0\n",
    "                while j < len(t) and t[j] == ch:\n",
    "                    cntj += 1\n",
    "                    j += 1\n",
    "                \n",
    "                if cnti < cntj:\n",
    "                    return False\n",
    "                \n",
    "                if cnti != cntj and cnti < 3:\n",
    "                    return False\n",
    "                \n",
    "            return i == len(s) and j == len(t)\n",
    "        return sum(int(expand(s, word)) for word in words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def check(s,s2):\n",
    "            N1,N2 = len(s),len(s1)\n",
    "            i,j = 0,0\n",
    "            # print(s,s1)\n",
    "            while i<N1 and j<N2:\n",
    "                # print(i,j)\n",
    "                \n",
    "                c1,c2 = 1,1\n",
    "                while i<N1-1 and s[i]==s[i+1]:\n",
    "                    c1+=1\n",
    "                    i+=1\n",
    "\n",
    "                while j<N2-1 and s1[j]==s1[j+1]:\n",
    "                    c2+=1\n",
    "                    j+=1\n",
    "                if s[i]==s1[j]:\n",
    "                    # print(i,j,c1,c2)\n",
    "                    if c1<c2 or (c1>c2 and c1<3):\n",
    "                        return 0\n",
    "                    i+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    return 0\n",
    "            if i==N1 and j==N2:\n",
    "                return 1\n",
    "            # print(i,j)\n",
    "            return 0\n",
    "\n",
    "\n",
    "        ret = 0\n",
    "        for s1 in words:\n",
    "            ret += check(s,s1)\n",
    "        \n",
    "        return ret \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        \n",
    "        \n",
    "        \n",
    "        # my solution ... \n",
    "        \n",
    "        def func(s):\n",
    "            arr = []\n",
    "            for ch in s:\n",
    "                if arr and arr[-1] != ch:\n",
    "                    arr.append(' ')\n",
    "                arr.append(ch)\n",
    "            return ''.join(arr).split()\n",
    "        \n",
    "        goal = func(s)\n",
    "        count = 0\n",
    "        for word in words:\n",
    "            word = func(word)\n",
    "            if len(word) != len(goal):\n",
    "                continue\n",
    "            if all(w[0]==g[0] and (len(w)==len(g) or (len(w)<len(g) and len(g)>=3)) for w, g in zip(word, goal)):\n",
    "                count += 1\n",
    "        return count\n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        def check(s, t) -> bool:\n",
    "            n, m = len(s), len(t)\n",
    "            if m > n:\n",
    "                return False\n",
    "            i, j = 0, 0\n",
    "            while i < n and j < m:\n",
    "                if s[i] != t[j]:\n",
    "                    return False\n",
    "                k = i\n",
    "                while k < n and s[k] == s[i]:\n",
    "                    k += 1\n",
    "                c1 = k - i\n",
    "                i, k = k, j\n",
    "                while k < m and t[k] == t[j]:\n",
    "                    k += 1\n",
    "                c2 = k - j\n",
    "                j = k\n",
    "                if c1 < c2 or (c1 < 3 and c1 != c2):\n",
    "                    return False\n",
    "            return i == n and j == m\n",
    "        return sum(check(s, t) for t in words)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def sep_seg(self,s:str)->list:\n",
    "        l = len(s)\n",
    "        if l<=1:\n",
    "            return s\n",
    "        begin = 0\n",
    "        s+=\"/n\"\n",
    "        segments = []\n",
    "        for i in range(1,l+1):\n",
    "            if s[i]!=s[i-1]:\n",
    "                segments.append(s[begin:i])\n",
    "                begin = i\n",
    "        return segments    \n",
    "\n",
    "\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        s_segments = self.sep_seg(s)\n",
    "        print(s_segments)\n",
    "        ans = 0\n",
    "        for word in words:\n",
    "            w_segments = self.sep_seg(word)\n",
    "            print(w_segments)\n",
    "            if len(w_segments) != len(s_segments):\n",
    "                continue\n",
    "            for i in range(len(w_segments)):\n",
    "                if len(s_segments[i]) < len(w_segments[i]):\n",
    "                    break\n",
    "                if s_segments[i][0] != w_segments[i][0]:\n",
    "                    break\n",
    "                if s_segments[i]!=w_segments[i] and len(s_segments[i])<3:\n",
    "                    break\n",
    "            else:\n",
    "                ans += 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        res = 0\n",
    "        m = len(s)\n",
    "        for word in words:\n",
    "            p, q = 0, 0\n",
    "            n = len(word)\n",
    "            flag = True\n",
    "            while p < m and q < n:\n",
    "                if s[p] != word[q]:\n",
    "                    flag = False\n",
    "                    break\n",
    "                c = 1\n",
    "                while q+1<n and word[q] == word[q+1]:\n",
    "                    q+=1\n",
    "                    c+=1 \n",
    "                d = 1\n",
    "                while p+1<m and s[p] == s[p+1]:\n",
    "                    p+=1\n",
    "                    d+=1\n",
    "                # print(p,q,d,c)\n",
    "                if d < c or (d > c and d < 3):\n",
    "                    flag = False\n",
    "                    break\n",
    "                p += 1\n",
    "                q += 1\n",
    "            if p>=m and q>=n and flag:\n",
    "                res+=1\n",
    "        return res\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        #双指针模拟(还挺麻烦的)\n",
    "        n=len(s)\n",
    "        ans=0\n",
    "        for word in words:\n",
    "            i,j,m=0,0,len(word)\n",
    "            while i<n and j<m:\n",
    "                if s[i]!=word[j]:\n",
    "                    break\n",
    "                a,b=i,j\n",
    "                while j<m and word[j]==word[b]:\n",
    "                    j+=1\n",
    "                while i<n and s[i]==s[a]:\n",
    "                    i+=1\n",
    "                cur1,cur2=i-a,j-b\n",
    "                if cur2>cur1 or (cur2<cur1 and cur1<3):\n",
    "                    break\n",
    "            else:\n",
    "                if i==n and j==m:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "\n",
    "        def treat(s):\n",
    "            n = len(s)\n",
    "            s += ' ' # 方便处理边界\n",
    "            f = []\n",
    "            i, j = 0, 0\n",
    "            while i < n:\n",
    "                for j in range(i, n+1):\n",
    "                    if s[i] != s[j]:\n",
    "                        f.append([s[i], j-i]) # [0] = char, [1] = len\n",
    "                        i = j\n",
    "                        break\n",
    "            return f\n",
    "        \n",
    "        base = treat(s)\n",
    "        n = len(base)\n",
    "        ans = 0\n",
    "        for str0 in words:\n",
    "            tmp = treat(str0)\n",
    "            if n != len(tmp):\n",
    "                continue\n",
    "            needadd = True\n",
    "            for i in range(n):\n",
    "                if base[i][0] != tmp[i][0] or \\\n",
    "                (base[i][1] < 3 and tmp[i][1] != base[i][1]) or \\\n",
    "                base[i][1] < tmp[i][1]:\n",
    "                    needadd = False\n",
    "                    break\n",
    "            \n",
    "            if needadd:\n",
    "                ans += 1\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\r\n",
    "        chars=[]\r\n",
    "        cnt=1\r\n",
    "        pre=s[0]\r\n",
    "        for c in s[1:]:\r\n",
    "            if c==pre:\r\n",
    "                cnt+=1\r\n",
    "            else:\r\n",
    "                chars.append([pre,cnt])\r\n",
    "                pre=c\r\n",
    "                cnt=1\r\n",
    "        chars.append([c,cnt])\r\n",
    "        \r\n",
    "        ret=0\r\n",
    "        N=len(chars)\r\n",
    "        for word in words:\r\n",
    "            sid=0\r\n",
    "            idx=0\r\n",
    "            L=len(word)\r\n",
    "            expanded=False\r\n",
    "            while sid<N and idx<L:\r\n",
    "                cnt=0\r\n",
    "                cur,t_cnt=chars[sid]\r\n",
    "                while idx<L and word[idx]==cur:\r\n",
    "                    idx+=1\r\n",
    "                    cnt+=1\r\n",
    "                if cnt==0 or cnt>t_cnt or (t_cnt<3 and t_cnt!=cnt):\r\n",
    "                    break\r\n",
    "                if t_cnt>=3 and t_cnt>cnt:\r\n",
    "                    expanded=True\r\n",
    "                sid+=1\r\n",
    "\r\n",
    "            else:\r\n",
    "                if sid==N and idx==L and expanded:\r\n",
    "                    ret+=1\r\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import re  # use re module to process regular expression matching problems\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, S: str, words) -> int:\n",
    "        pattern = '^'  # '^' match the start of target word\n",
    "        a = [i for i in range(len(S)) if i == 0 or S[i] != S[i-1]] + [len(S)]  # record the start indexes of continuous same letter; e.g.'aaabbcc': [0, 3, 5]\n",
    "        # print(a)\n",
    "        for i in range(1, len(a)):\n",
    "            cha, num = S[a[i]-1], a[i] - a[i-1]  # cha is the continuous same letters, num is length\n",
    "            print(cha, num)\n",
    "            if num < 3: \n",
    "                pattern += cha * num  # if num < 3, it means not stretchy, so the regular expression should be this 'cha' itself\n",
    "            if num >= 3:\n",
    "                pattern += '%s{1,%d}' % (cha, num)  # if num > 3, it means any length that not longer than num (but need to exist) could be OK, so the regular expression is '%s{1,%d}'\n",
    "        pattern += '$' # '$' match the end of target word\n",
    "        # print(pattern)\n",
    "        res = 0 # use res as a count\n",
    "        for word in words:\n",
    "            if re.match(pattern, word):\n",
    "                res += 1 # use regular expression to match word in words one by one\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        #双指针模拟计数(还挺麻烦的)\n",
    "        n=len(s)\n",
    "        ans=0\n",
    "        for word in words:\n",
    "            i,j,m=0,0,len(word)\n",
    "            while i<n and j<m:\n",
    "                if s[i]!=word[j]:\n",
    "                    break\n",
    "                a,b=i,j\n",
    "                while j<m and word[j]==word[b]:\n",
    "                    j+=1\n",
    "                while i<n and s[i]==s[a]:\n",
    "                    i+=1\n",
    "                cur1,cur2=i-a,j-b\n",
    "                if cur2>cur1 or (cur2<cur1 and cur1<3):\n",
    "                    break\n",
    "            else:\n",
    "                if i==n and j==m:\n",
    "                    ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def expressiveWords(self, s: str, words: List[str]) -> int:\n",
    "        s2 = ['^', s[0]]\n",
    "        pre, cnt = s[0], 1\n",
    "        for ch in s[1:]:\n",
    "            if ch != pre:\n",
    "                if cnt < 3:\n",
    "                    s2.append(f\"{{{cnt}}}\")\n",
    "                else:\n",
    "                    s2.append(f\"{{1,{cnt}}}\")\n",
    "                cnt = 1\n",
    "                pre = ch\n",
    "                s2.append(f\"{ch}\")\n",
    "            else:\n",
    "                cnt += 1\n",
    "        if cnt < 3:\n",
    "            s2.append(f\"{{{cnt}}}$\")\n",
    "        else:\n",
    "            s2.append(f\"{{1,{cnt}}}$\")\n",
    "        s2 = \"\".join(s2)\n",
    "        return sum(1 for w in words if re.match(s2, w))\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
